"""AcyclicReachability.py

Bit-parallel algorithm for testing which vertices can reach which other
vertices in a DAG.

Usage:
    R = Reachability(G)
    ...
    R.reachable(source,destination)
returns a boolean value: True if G contains a path from the source vertex
to the destination vertex, and False otherwise. The initialization of R
performs a linear number of bitvector operations, after which each reachability
test takes constant time to perform.

D. Eppstein, April 2009.
"""

from .partial_order import TopologicalOrder


class Reachability:

    def __init__(self, G):
        """Initialize a reachability data structure for the given DAG."""
        self.key = {}
        self.canReach = []
        L = TopologicalOrder(G)
        L.reverse()
        for v in L:
            k = self.key[v] = len(self.canReach)
            bits = 1 << k
            for w in G[v]:
                bits |= self.canReach[self.key[w]]
            self.canReach.append(bits)

    def reachable(self, source, destination):
        """Test whether the DAG has a path from source to destination."""
        return ((1 << self.key[destination]) & self.canReach[self.key[source]]
                != 0)
